COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00005 ENDMK
C⊗;

(DE APPEND (X Y)		;builds up structure from the outside
     (COND ((NULL X) Y)
	   (T (CONS (CAR X) 
       		    (APPEND (CDR X) Y)))))

(DE LENGTH (L)			;adds 1 from the outside
      (COND ((NULL L) 0)
	    (T (ADD1 (LENGTH (CDR L))))))

or:

(DE LENGTH (L)(LEN1 L 0))	; this pair  adds up from the inside
(DE LEN1 (L N)			; essentially "iterative"
    (COND ((NULL L) N)
	  (T (LEN1 (CDR L) (ADD1 N)))))

(DE SUBST (X Y Z)		; similar to  APPEND in structure
	(COND ((ATOM Z) (COND ((EQ  Y Z) X) 
			      (T Z)))
	      (T (CONS (SUBST X Y (CAR Z))
		       (SUBST X Y (CDR Z))))))


(DE FIB(N) (COND ((EQ N 0) 1)
		 ((EQ N 1) 1)
		 (T (PLUS (FIB (DIF N 2))
			  (FIB (DIF N 1))))))

(DE MEMBER (X L)(COND ((NULL L) NIL)	; note, T and NIL are representing true
		      ((EQUAL (CAR L) X) T) ; and false.
		      (T (MEMBER X (CDR L)))))

(DE PLUS (X Y)
	(COND ((EQ X 0) Y)
	      (T (PLUS (SUB1 X) 
		       (ADD1 Y)))))

where:
(DE SUB1 (X) (COND ((EQ X 0) error)
		   (T (PRED X 0))))

(DE PRED (X Y)				; a bit tricky --just find the predecessor
	(COND ((EQ (ADD1 Y) X) X)
	      (T (PRED X (ADD1 Y)))))


(DE TIMES (X Y)
   (COND ((EQ X 0) 0)
	 (T (TIMES (SUB1 X)
		   (PLUS  X Y)))))
		     

(DE REVERSE (X) (REV1 X ())	;this pair builds up  reversal in second arg.
(DE REV1 (X Y)
	(COND ((NULL X) Y)
	      (T (REV1 (CDR X)
		       (CONS (CAR X) Y)))))

or
(DE REVERSE (X)(APPEND (REVERSE (CDR X))	; this pair is a loss
		       (LIST (CAR X))))		; since much structure is built
						; and discarded